A computer network is a geographically distributed collection of interconnected communication links and segments for transporting data between nodes, such as computers. Many types of network segments are available, with the types ranging from local area networks (LAN) to wide area networks (WAN). For example, the LAN may typically connect personal computers and workstations over dedicated, private communications links, whereas the WAN may connect large numbers of nodes over long-distance communications links, such as common carrier telephone lines. The Internet is an example of a WAN that connects disparate networks throughout the world, providing global communication between nodes on various networks. The nodes typically communicate over the network by exchanging discrete frames or packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Computer networks may be further interconnected by an intermediate network node, such as a switch or router, having a plurality of ports that may be coupled to the networks. To interconnect dispersed computer networks and/or provide Internet connectivity, many organizations rely on the infrastructure and facilities of Internet Service Providers (ISPs). ISPs typically own one or more backbone networks that are configured to provide high-speed connection to the Internet. To interconnect private networks that are geographically diverse, an organization may subscribe to one or more ISPs and couple each of its private networks to the ISP's equipment. Here, the router may be utilized to interconnect a plurality of private networks or subscribers to an IP “backbone” network. Routers typically operate at the network layer, i.e., layer 3, of a communications protocol stack, such as the internetwork layer of the Transmission Control Protocol/Internet Protocol (TCP/IP) communications architecture.
Simple networks may be constructed using general-purpose routers interconnected by links owned or leased by. ISPs. As networks become more complex with greater numbers of elements, additional structure may be required. In a complex network, structure can be imposed on routers by assigning specific jobs to particular routers. A common approach for ISP networks is to divide assignments among access routers and backbone routers. An access router provides individual subscribers access to the network by way of large numbers of relatively low-speed ports connected to the subscribers. Backbone routers, on the other hand, provide transports to Internet backbones and are configured to provide high forwarding rates on fast interfaces. ISPs may impose further physical structure on their networks by organizing them into points of presence (PoP). An ISP network usually consists of a number of PoPs, each of which comprises a physical location wherein a set of access and backbone routers is located.
As Internet traffic increases, the demand for access routers to handle increased density and backbone routers to handle greater throughput becomes more important. In this context, increased density denotes a greater number of subscriber ports that can be terminated on a single router. Such requirements can be met most efficiently with platforms designed for specific applications. An example of such a specifically designed platform is an aggregation router. The aggregation router is an access router configured to provide high quality of service and guaranteed bandwidth for both data and voice traffic destined for the Internet. The aggregation router also provides a high degree of security for such traffic. These functions are considered “high-touch” features that necessitate substantial processing of the traffic by the router. More notably, the aggregation router is configured to accommodate increased density by aggregating a large number of leased lines from ISP subscribers onto a few trunk lines coupled to an Internet backbone.
In a typical implementation of a router, a processor is provided to process an original header of a packet while leaving the remainder of the packet, i.e., the “trailer”, unchanged. In a high-end router implementation using a network processor, dedicated hardware is provided to efficiently pass the original packet header to a forwarding engine. The forwarding engine may be implemented as a “chip”, e.g., an application specific integrated circuit (ASIC), comprising a plurality of processors and memories. Each memory, i.e., a header buffer, is configured to temporarily store (hold) the packet header as it is processed (modified) by a processor. This eliminates time that would otherwise be wasted waiting to fetch portions of the header from an external device or storage. Only the original packet header is brought “on-chip” to reduce the memory and bandwidth requirements for the forwarding engine; the packet trailer is held in an external, lower-cost memory of the dedicated hardware. The trailer is thereafter rejoined (merged) with a modified packet header computed by the processors.
The modifications made to the original packet header typically include removal of a layer 2 header associated with an ingress port of the router, modification of specific fields of the header and the addition of a new, modified layer 2 header associated with an egress port of the router. Often the packet may be carried within a “tunnel” (e.g., GRE, IP/IP or IPSEC) that contributes to the number and length of headers that must be removed and/or added by the processors. Therefore, the sizes of the original and modified headers may be different. However, the actual length of the original packet header is generally not known until processing begins. As a result, a worst case header length is always passed to the forwarding engine and the size of each header buffer must be sufficient to handle this “longest” original packet header. The on-chip header buffer must also be large enough to hold a largest resulting header length.
Other information that is typically passed to the forwarding engine along with the packet header may include interface and queue state information. A portion of the on-chip header buffer is also used to store output commands that instruct external direct memory access (DMA) logic where to move the header from the on-chip buffer when merging it with the packet trailer in a bulk external memory or when de-queuing packets. For an implementation wherein the processors operate in a serial “pipeline” configuration, each processor typically performs a part of the total packet processing. In such an implementation, additional state information may be passed within the on-chip buffer “space” from one processor to the next.
Often, a substantial portion of the original packet header is unchanged or unmodified. Copying of this portion of the original header from one location to another within the header buffer is expensive in terms of processor cycles and on-chip buffer space. Therefore, it is desirable to manage the on-chip header buffer to avoid these copies and to minimize the header buffer size. This is particularly desirable when the forwarding engine ASIC contains many processors, each having one or more on-chip buffers configured to hold packet headers that are passed from processor to processor.